rtk 2002

2002.1.1 (popravi)

1. podnaloga

Naročniki večjih količin tovora se običajno odločajo za prevoz tovora z ladjo. Ko zabojniki prispejo v luko, jih morajo tam uskladiščiti, vse dokler ponje ne pride naročnik ali pa jih morajo natovoriti na vlak. V neki luki zabojnike nalagajo enega ob drugega in ko zapolnijo celo vrsto, se lotijo nalaganja v drugo vrsto, nato tretjo in tako dalje. Ko se zapolni cela površina, začnejo zabojnike nalagati še na naslednjo višino v enakem zaporedju kot prej (torej prvi zabojnik na drugi višini pride položen na prvi zabojnik v prvi višini itd.). Podano imamo število zabojnikov v vsaki vrsti $n$, število vrst v vsaki plasti $m$ in število plasti $l$.

Naloga

Popravi program zabojnik tako, da bo za dane $n$, $m$ in $l$ ter za neko številko zabojnika izračunal, v kateri plasti in v kateri vrsti je ta zabojnik ter kateri v svoji vrsti je (stolpec). Vse troje se šteje od 1 naprej in to v takem vrstnem redu, da manjše številke predstavljajo tiste dele skladišča, ki so bili zapolnjeni prej.

def zabojnik(n,m,l,z):

    plast = (z - 1) / (n * m)
    vrsta = 1 + ((z - 1) // (n * m)) / n
    stolpec = 1 + ((z - 1) % (n * m)) / n

    izpis = 'Plast: ' + str(int(plast)) + ', '
    izpis += 'Vrsta: ' + str(int(vrsta)) + ','
    izpis += 'Stolpec: ' + str(int(stolpec))
    return izpis

Primer postavitve zabojev v plasteh za $n=4$, $m=3$, $l=2$:

| 1 2  3  4  |     | 13 14 15 16 |     | 25 26 27 28 |
| 5 6  7  8  |     | 17 18 19 20 |     | 29 30 31 32 |
| 9 10 11 12 |     | 21 22 23 24 |     | 33 34 35 36 |

Zabojnik s številko 16 na gornji sliki je četrti zabojnik v prvi vrsti druge plasti.

Vhodni podatki

Števila $m$,$n$,$l$ ter številka zabojnika, katerega položaj nas zanima.

Izhodni podatki

Položaj zabojnika (plast, vrsta, stolpec) v obliki niza.

Primer

Vhod

>>>>zabojnik(4,3,2,16)

Izhod

'Plast: 2, Vrsta: 1, Stolpec: 4'

Uradna rešitev

def zabojnik(n,m,l,z):

    plast = 1 + (z - 1) / (n * m)
    vrsta = 1 + ((z - 1) % (n * m)) / n
    stolpec = 1 + ((z - 1) % (n * m)) % n

    izpis = 'Plast: ' + str(int(plast)) + ', '
    izpis += 'Vrsta: ' + str(int(vrsta)) + ', '
    izpis += 'Stolpec: ' + str(int(stolpec))
    return izpis

2002.1.2 (popravi)

1. podnaloga

Liliput je majhno mesto z veliko avtobusnimi postajami. Vse proge mestnih avtobusov so krožne. Vsaka postaja pa pripada natančno eni progi, torej nobena dva avtobusa nikoli ne obiščeta iste avtobusne postaje. Težava je v tem, da Liliputanci objavljajo vozne rede svojih avtobusov na prav poseben način. Avtobusne postaje so oštevilčene s števili od $1$ do $N$, opis vseh prog v njihovem mestu pa predstavijo kot zaporedje $N$ števil.

Za primer vzemimo zaporedje števil $[8, 10, 6, 3, 9, 4, 2, 5, 1, 7]$, ki ga lahko predstavimo kot:

$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 8 & 10 & 6 & 3 & 9 & 4 & 2 & 5 & 1 & 7 \end{pmatrix}$

Prvo število v zaporedju je $8$, kar pomeni, da gre avtobus, ki odpelje s postaje $1$, na postajo $8$. Osmo število v zaporedju je 5, kar pomeni, da avtobus, ki pripelje na postajo številka $8$, nadaljuje svojo pot do postaje številka $5$; peto število je $9$, zato avtobus nadaljuje pot do postaje $9$ in tako naprej, dokler se ne vrne na začetno postajo. Iz gornjega zaporedja lahko po tem postopku izluščimo tri krožne avtobusne proge: $[1, 8, 5, 9], [2, 10, 7], [3, 6, 4]$

Naloga

Tvoja naloga je popraviti program avtobus, ki bo nevajenemu tujcu za poljubno zaporedje števil izpisal vse proge mestnih avtobusov ter mu povedal, koliko postaj ima najdaljša proga. Na voljo je seznam dolžine $N$, ki vsebuje poljubno zaporedje števil, ki ustreza opisu prog mestnih avtobusov.

def avtobus(vozni_red):

    N = len(vozni_red)
    obiskane_postaje = [False for i in range(N)]
    najdaljsa_proga = 0
    proge = []

    for j in range(N):
        if obiskane_postaje[j]:
            obiskane_postaje[j] = True
            proga = [j]
            k = vozni_red[j]
            while k != j:
                proga.append(k)
                obiskane_postaje[k] = True
                k = vozni_red[k-1]
            proge.append(proga)

        if len(proga) > najdaljsa_proga:
            najdaljsa_proga = len(proga)
    proge.append(najdaljsa_proga)
    return proge

Vhodni podatki

Zaporedje števil, podano v seznamu.

Omejitve vhodnih podatkov

• $1 \leq N \leq 10^6$
  $N$ = število postaj

Izhodni podatki

Seznam z vsemi avtobusnimi programi predstavljenimi kot seznam postaj. Zadnji element seznama pa je dolžina najdaljše proge.

Primer

Vhod

>>>>avtobus([8, 10, 6, 3, 9, 4, 2, 5, 1, 7])

Izhod

[[1, 8, 5, 9], [2, 10, 7], [3, 6, 4], 4]

Uradna rešitev

def avtobus(vozni_red):

    N = len(vozni_red)
    obiskane_postaje = [False for i in range(N)]
    najdaljsa_proga = 0
    proge = []

    for j in range(N):
        if not obiskane_postaje[j]:
            obiskane_postaje[j] = True
            proga = [j+1]
            k = vozni_red[j]
            while k != j+1:
                proga.append(k)
                obiskane_postaje[k-1] = True
                k = vozni_red[k-1]
            proge.append(proga)

        if len(proga) > najdaljsa_proga:
            najdaljsa_proga = len(proga)
    proge.append(najdaljsa_proga)
    return proge

2002.1.3 (popravi)

1. podnaloga

Pri uporabi bančne kartice moramo dokazati, da poznamo kodo pin (osebno identifikacijsko številko). Podobno v deželi PinLand uporabljajo štirimestne črkovne kode pin tudi za dostop do pomembnih podatkov na mreži. Pri razbijanju kode pin si pomagajmo s poskušanjem: vemo, kakšne so dovoljene kode, in preizkusimo vse možnosti.

Za testiranje je na voljo funkcija test, ki sprejme kodo v obliki niza in vrne True če je koda pravilna ter False če ni.

Za kodo pin veljata naslednji omejitvi:

• dolga je točno štiri znake;
• dovoljeni so le znaki A, . . . , Z, torej ravno vse velike črke angleške abecede.

Naloga

Popravi program pin, ki bo s poskušanjem odkril pravo kodo pin in jo izpisal.

def pin():
    '''Funkcija s pomočjo funkcije test in poskušanjem najde pravo pin in jo izpiše.'''

    mozni_znaki = 'ABCDEFGHIJKLmnoPQRSTUVWXYZ'
    poskus = [0,0,0,0]
    for a in mozni znaki:
        poskus[0] = a
        for b in mozni_znaki:
            poskus[1] = b
            for c in mozni_znaki:
                poskus[2] = c
                for d in mozni_znaki:
                    poskus[3] = c

                    poskus_str = ' '.join(poskus)
                    if test(poskus_str):
                        return poskus_str

Vhodni podatki

Funkcija nima vhodnega podatka.

Izhodni podatki

Niz štirih znakov, ki predstavljajo pravo pin kodo.

Uradna rešitev

def test(poskus):
    '''Funkcija vrne True, če je pin pravilen in False sicer.'''

    st = [66,90,88,65,78,30]
    stevec = 0
    for i in poskus[::-1]:
        a = ord(i)
        if a == st[stevec]:
            stevec += 1
        else:
            return False
    return True


def pin():
    '''Funkcija s pomočjo funkcije test in poskušanjem najde pravo pin in jo izpiše.'''

    mozni_znaki = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    poskus = [0,0,0,0]
    for a in mozni_znaki:
        poskus[0] = a
        for b in mozni_znaki:
            poskus[1] = b
            for c in mozni_znaki:
                poskus[2] = c
                for d in mozni_znaki:
                    poskus[3] = d

                    poskus_str = ''.join(poskus)
                    if test(poskus_str):
                        return poskus_str